const Text = Symbol(); // 文本节点

const Comment = Symbol(); // 注释节点

const Fragment = Symbol(); // 注释节点

const getSequence = (arr) => {
    const p = arr.slice();
    const result = [0];
    let i, j, u, v, c;
    const len = arr.length;
    for(i = 0; i < len; i ++) {
        const arrI = arr[i];
        if (arrI !== 0) {
            p[i] = j;
            result.push(i);
            continue;
        }
        u = 0;
        v - result.length - 1;
        while(u < v) {
            c = ((u + v) / 2) | 0;
            if(arr[result[c]] < arrI) {
                u = c + 1;
            } else {
                v = c;
            }
        }
        if (arrI < arr[result[u]]) {
            if (u > 0) {
                p[i] = result[u - 1];
            }
            result[u] = i;
        }
    }
    u = result.length;
    v = result[u - 1];
    while(u -- > 0) {
        result[u] = v;
        v = p[v];
    }
    return result;
} 

const createRenderer = (options) => {

    const  { 
        setElementText, 
        createElement, 
        insert,
        createText,
        setText,
        patchProps
    } = options;

    const mountElement = (vnode, container, anchor) => {
        const el = vnode.el = createElement(vnode.type);

        if (typeof vnode.children === 'string') {
            setElementText(el, vnode.children);
        } else if (Array.isArray(vnode.children)) {
            vnode.children.forEach(child => {
                patch(null, child, el)
            })
        }

        if (vnode.props) {
            for(const key in vnode.props) {
                patchProps(el, key, null, vnode.props[key])
            }
        }

        insert(el, container, anchor);
    };

    // diff算法用来比较两组子元素的差异，能最大程度的复用DOM节点
    // 单端diff
    const singleDiff = (n1, n2, container) => {

        const oldChildren = n1.children;
        const newChildren = n2.children;

        let lastIndex = 0;

        // 通过key，找到可复用的节点，移动并更新可复用的节点
        for (let i = 0; i < newChildren.length; i ++) {
            const newVNode = newChildren[i];
            let find = false;
            for(let j = 0; j < oldChildren.length; j ++) {
                const oldVNode = oldChildren[j];
                if (newVNode.key === oldVNode.key) {
                    find = true;
                    // 更新可复用节点
                    patch(oldVNode, newVNode, container);

                    // 移动可复用节点
                    if (j < lastIndex) {
                        // 说明当前节点真实DOM需要移动
                        const prevVNode = newChildren[i - 1];
                        if (prevVNode) {
                            const anchor = prevVNode.el.nextSibling;
                            insert(container, newVNode, anchor);
                        }
                    } else {
                        lastIndex = j;
                    }

                    break;
                }
            }
            // 新增节点
            if (!find) {
                const prevVNode = newChildren[i - 1];
                let anchor = null;
                if (prevVNode) {
                    anchor = prevVNode.el.nextSibling;
                } else {
                    anchor = container.firstChild;
                }
                patch(null, newVNode, container, anchor);
            }
        }

        // 删除旧节点
        for(let i = 0; i < oldChildren.length; i ++) {
            const oldVNode = oldChildren[i];
            const has = newChildren.includes(vnode => vnode.key === oldVNode.key);
            if (!has) {
                unmount(oldVNode)
            }
        }

    }

    // 双端diff
    const doubleDiff  = (n1, n2, container) => {
        
        const oldChildren = n1.children;
        const newChildren = n2.children;
        
        // 端点
        let oldStartIdx = 0;
        let newStartIdx = 0;
        let oldEndIdx = oldChildren.length - 1;
        let newEndIdx = newChildren.length - 1;

        let oldStartVNode = oldChildren[oldStartIdx];
        let oldEndVNode = oldChildren[oldEndIdx];
        let newStartVNode = newChildren[newStartIdx];
        let newEndVNode = newChildren[newEndIdx];

        while(oldEndIdx > oldStartIdx && newEndIdx > newStartIdx) {
            if (oldStartVNode.key === newStartVNode.key) {
                patch(oldStartVNode, newStartVNode, container);
    
                oldStartVNode = oldChildren[++oldStartIdx];
                newStartVNode = newChildren[++newStartIdx];
            } else if (oldStartVNode.key === newEndVNode.key) {
                patch(oldStartVNode, newEndVNode, container);
                insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling);

                oldStartVNode = oldChildren[++oldStartIdx];
                newEndVNode = newChildren[--newEndIdx];
    
            } else if (oldEndVNode.key === newStartVNode.key) {
                patch(oldEndVNode, newStartVNode, container);
    
                insert(oldEndVNode.el, container, oldStartVNode.el);
    
                oldEndVNode = oldChildren[--oldEndIdx];
                newStartVNode = newChildren[++newStartIdx];
            } else if (oldEndVNode.key === newEndVNode.key) {
                patch(oldEndVNode, newEndVNode, container);
    
                oldEndVNode = oldChildren[--oldEndIdx];
                newEndVNode = newChildren[--newEndIdx];
            } else {
                const idxInOld = oldChildren.findIndex(node => node.key === newStartVNode.key);
                if (idxInOld) {
                    const vNodeToMove = oldChildren[idxInOld];
                    patch(vNodeToMove, newStartVNode, container);
                    insert(vNodeToMove.el, container, oldStartVNode.el);
                    oldChilren[idxInOld] = undefined;

                } else {
                    // 添加新元素
                    patch(null, newStartVNode, container, oldStartVNode.el);
                }
                newStartVNode = newChildren[++newStartIdx];
            }
        }
        if (oldEndIdx < oldStartIdx && newEndIdx > newStartIdx) {
            // 添加新节点
            for(let i = newStartIdx; i <= newEndIdx; i ++) {
                const anchor = newChildren[newEndIdx + 1] ? newChildren[newEndIdx + 1].el : null;
                patch(null, newChildren[i], container, anchor);
            }
        } else if(newEndIdx < newStartIdx && oldEndIdx > oldStartIdx) {
            // 移除不存在的元素
            for(let i = oldStartIdx; i <= oldEndIdx; i ++) {
                unmount(oldChildren[i])
            }
        }
    }

    // 快速diff 最早应用于ivi、inferno框架
    const fastDiff  = (n1, n2, container) => {

        const oldChildren = n1.children;
        const newChildren = n2.children;

        // i. 预处理部分 提取相同的前缀及后缀
        let j = 0;
        let oldVNode = oldChildren[j];
        let newVNode = newChildren[j];
        while(oldVNode.key === newVNode.key) { // 前缀处理
            patch(oldVNode, newVNode, container);
            j ++;
            oldVNode = oldChildren[j];
            newVNode = newChildren[j];
        }

        let oldEnd = oldChildren.length - 1;
        let newEnd = newChildren.length - 1;
        oldVNode = oldChildren[oldEnd];
        newVNode = newChildren[newEnd];
        while(oldVNode.key === newVNode.key) { // 后缀处理
            patch(oldVNode, newVNode, container);
            oldEnd--;
            newEnd--;
            
            oldVNode = oldChildren[oldEnd];
            newVNode = newChildren[newEnd];
        }
        if (j > oldEnd && newEnd > j) { // 说明[i, newEnd] 范围的节点是新增节点
            const anchorIndex = newEnd + 1;
            const anchor = anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null;
            while(j <= newEnd) {
                patch(null, newChildren[i++], container,anchor);
            }
        } else if (j > newEnd && oldEnd > j) { // 说明[i, oldEnd] 范围的节点是待删除节点
            while(j <= newEnd) {
                unmount(oldChildren[j ++]);
            }
        } else { 
            // ii. 非理想情况的diff处理， 需要处理 新增、待删除、待移动的元素
            const count = newEnd - j + 1;
            const source = new Array(count).fill(-1);
            
            const oldStart = j;
            const newStart = j;
            let keyIndex = {};
            let moved = false;
            let pos = 0;
            let patched = 0;
            for (let i = newStart; i <= newEnd; i ++) {
                keyIndex[newChildren[i].key] = i;
            }

            for (let i = oldStart; i <= oldEnd; i ++) {
                const oldVNode = oldChildren[i];
                
                if (patched < count) { // 节约性能
                    const k = keyIndex[oldVNode.key];
                    
                    if (typeof keyIndex[oldVNode.key] !== 'undefined') {
                        const newVNode = newChildren[k];
                        patch(oldVNode, newVNode, container);
                        source[k - newStart] = i;
    
                        // 找到待移动的节点
                        if (k < pos) {
                            moved = true;
                            // 待移动
                        } else {
                            pos = k;
                        }
                    } else {
                        unmount(oldVNode); // 删除旧元素
                    }
                } else {
                    unmount(oldVNode); // 删除旧元素
                }
            }

            if(moved) {
                // 计算最长公共子序列
                const seq = getSequence(source);

                let s = seq.length - 1;
                let i = count -1;
                for(i; i >= 0; i --) {
                    if (source[i] === -1) { // 新增子元素
                        const pos = i + newStart;
                        const newVNode = newChildren[pos];
                        const nextPos = pos + 1;
                        const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null;
                        patch(null, newVNode, container, anchor);
                    } else if (i !== seq[s]) {
                        // 不在最长公共子序列里，则需要移动
                        const pos = i + newStart;
                        const newVNode = newChildren[pos];
                        const nextPos = pos + 1;
                        const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null;
                        insert(newVNode, container, anchor);
                    } else {
                        s --;
                    }
                }
            }

        }

    }
    
    const patchChildren = (n1, n2, container) => {

        // 共有三种类型子节点
        // 1. 字符串
        // 2. 一个数组，内部包括多个元素
        // 3. 什么都没有
        // 故替换子元素时共有3*3种场景（三种类型的旧节点以及三种类型的新节点）

        if (typeof n2.children === 'string') {
            if (Array.isArray(n1.children)) {
                n1.children.forEach(node => unmount(node));
                return;
            }
            setElementText(container, n2.children);
        } else if (Array.isArray(n2.children)) {
            if (Array.isArray(n1.children)) {

                // // I. 卸载所有旧元素， 插入所有新元素，待优化为diff算法
                // n1.children.forEach(c => unmount(c));
                // n2.children.forEach(c => patch(null, c, container));

                // // II. 更新每个元素, 以减少DOM操作次数
                // const oldChildren = n1.children;
                // const newChildren = n2.children;

                // const commonLen = math.min(oldChildren.length, newChildren.length);

                // for (let i = 0; i < commonLen; i ++) {
                //     patch(oldChildren[i], newChildren[i], container)
                // }
                // if (newChildren.length > oldChildren.length) {
                //     for(let i = commonLen; i < newChildren.length; i ++) {
                //         patch(null, newChildren[i], container);
                //     }
                // }
                // if (oldChildren.length > newChildren.length) {
                //     for(let i = commonLen; i < oldChildren.length; i ++) {
                //         unmount(oldChildren[i]);
                //     }
                // }

                // III. 移动DOM - 单端diff
                // singleDiff(n1, n2, container);

                // IV. 移动DOM - 双端diff
                // doubleDiff(n1, n2, container);

                // V. 移动DOM - 快速diff
                fastDiff(n1, n2, container);
            } else {
                setElementText(container, '');
                n2.children.forEach(c => patch(null, c, container));
            }
        } else {
            if (Array.isArray(n1.children)) {
                n1.children.forEach(c => unmount(c));
            } else if(typeof n1.children === 'string') {
                setElementText(container, '');
            }
        }
    }

    const patchElement = (n1, n2) => {
        const el = n2.el = n1.el;
        const oldProps = n1.props;
        const newProps = n2.props;
        // 1. 更新props
        for (const key in newProps) {
            if (newProps[key] !== oldProps[key]) {
                patchProps(el, key, oldProps[key], newProps[key]);
            }
        }

        for (const key in oldProps) {
            if (!(key in newProps)) {
                patchProps(el, key, oldProps[key], null);
            }
        }

        // 2. 更新children
        patchChildren(n1, n2, el);
    }

    const patch = (n1, n2, container, anchor) => {
        if (n1 && n1.type !== n2.type) {
            unmount(n1);
            n1 = null;
        };

        const { type } = n2;
        if (typeof type === 'string') {
            // 正常的标签
            if (!n1) {
                mountElement(n2, container, anchor);
            } else {
                patchElement(n1, n2, container);
            }
        } else if (typeof type === 'object') {
            // 组件渲染
        } else if (type === Text) {
            if (!n1) {
                const el = n2.el = createText(n2.children)
                insert(container, el);
            } else {
                const el = n2.el = n1.el;
                if (n2.children !== n1.children) {
                    setText(el, n2.children)
                }
            }

        } else if (type === Comment) {
            // 类似于文本节点
        } else if(type === Fragment) {
            if (!n1) {
                n2.children.forEach(c => patch(null, c, container));
            } else {
                patchChildren(n1, n2, container);
            }

        }
        // ... 其他处理
        
    };

    const unmount = (vnode) => {
        if (vnode.type === Fragment) {
            vnode.children.forEach(c => unmount(c));
            return ;
        }
        const parent = vnode.el.parentNode;
        if (parent) parent.removeChild(el);
        // 解除该元素绑定的事件、若该元素是组件，触发对应生命周期、触发绑定在该元素上的生命周期
        // ...
    }



    // 不同平台用不同的渲染方法
    const render = (vnode, container) => {
        if (vnode) {
            patch(container._vnode, vnode, container);
        } else {
            if (container._vnode) {
                // 卸载
                unmount(container._vnode)
            }
        }
        container._vnode = vnode;
    };
    const hydrate = (vnode, container) => {

    }
    return {
        render,
        hydrate
    }
};

const shouldSetAsProps = (el, key, value) => {
    if (key === 'form' && el.tagName === 'INPUT') return false; // input输入框form属性只读，因此不允许通过DOM Properties方式设置
    return key in el;
}


const renderer = createRenderer({
    createElement(tag) {
        return document.createElement(tag)
    },
    setElementText(el, text) {
        el.textContent = text;
    },
    insert(el, parent, anchor = null) {
        parent.insertBefore(el, anchor);
    },
    createText(text) {
       return document.createTextNode(text);
    },
    setText(el, text) {
        el.nodeValue = text;
    },
    patchProps(el, key, preValue, nextValue) {
        if (key === 'class') {
            el.className = nextValue || '';
        } else if (key.startWith('on')) { // 绑定事件
            const name = key.slice(2).toLowerCase();

            // preValue && el.removeEventListener(name, preValue); // 更新事件
            // el.addEventListener(name, nextValue);

            // 这么写👇 更新事件时无需removeEventListener
            let invokers = el._vei || (el._vei = {});
            const invoker = invokers[key];
            if (nextValue) {
                if (!invoker) {
                    if (e.timeStamp < invoker.attached)
                    invoker = el._vei[key] = (e) => {
                        if (Array.isArray(invoker.value)) {
                            invoker.value.forEach(fn => fn(e))
                        } else {
                            invoker.value(e)
                        }
                    }
                    invoker.value = nextValue;
                    invoker.attached = performance.now()
                    el.addEventListener(name, invoker);
                } else {
                    invoker.value = nextValue;
                }
            } else if (invoker) {
                el.removeEventListener(name, invoker)
            }

        } else if (shouldSetAsProps(el, key)) {
            const type = typeof el[key];
            if (type === 'boolean' && nextValue === '') { // 针对Boolean属性语法糖写法
                el[key] = true;
            } else {
                el[key] = nextValue;
            }
        } else {
            el.setAttibute(key, nextValue) // HTML Attribute 
        }

    }
});